/**
 * @author ChaP
 * @date 2019/04/22
 * @describe:
 */
package CodingTest.AC20190421;

/**
 * leetcode - 397
 * 给定一个正整数 n，你可以做如下操作：

 1. 如果 n 是偶数，则用 n / 2替换 n。
 2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
 n 变为 1 所需的最小替换次数是多少？
 */
public class integerReplacement {
    public int integerReplacement(int n){
        if(n == 1)return 0;

        if(n%2 == 0)//偶数
        {
            return 1+integerReplacement(n/2);

        }else{
            if(n==Integer.MAX_VALUE)
                return integerReplacement(n-1);
            return Math.min(1+integerReplacement(n-1),1+integerReplacement(n+1));

        }

    }

    public static void main(String[] args) {
        integerReplacement ir = new integerReplacement();
        int n =7;
        System.out.println(ir.integerReplacement(n));
    }
}
